SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Transitive relation</title>

</head>

Transitive relation

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox vcard"><caption class="infobox-title fn" style="padding-bottom:0.2em;">Transitive relation</caption><tbody><tr><th scope="row" class="infobox-label">Type</th><td class="infobox-data"><a href="Binary_relation" title="Binary relation">Binary relation</a></td></tr><tr><th scope="row" class="infobox-label">Field</th><td class="infobox-data"><a href="Elementary_algebra" title="Elementary algebra">Elementary algebra</a></td></tr><tr><th scope="row" class="infobox-label">Statement</th><td class="infobox-data">A relation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> on a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is transitive if, for all elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">, whenever <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> relates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> also relates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">.</td></tr><tr><th scope="row" class="infobox-label">Symbolic statement</th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}</annotation>

</semantics>

</math><img src="./547ea1f38f6a75fd73832fd0cc72b8c645258bb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.119ex; height:2.843ex;" alt="{\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}" loading="lazy"></td></tr></tbody></table>

In <a href="Mathematics" title="Mathematics">mathematics</a>, a <a href="Binary_relation" title="Binary relation">binary relation</a> R on a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c.

Every <a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a> and every <a href="Equivalence_relation" title="Equivalence relation">equivalence relation</a> is transitive. For example, less than and <a href="Equality_(mathematics)" title="Equality (mathematics)">equality</a> among <a href="Real_number" title="Real number">real numbers</a> are both transitive: If a < b and b < c then a < c; and if x = y and y = z then x = z.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .stack{box-sizing:border-box}.mw-parser-output .stack>div{margin:1px;overflow:hidden}@media all and (min-width:720px){.mw-parser-output .stack-clear-left{float:left;clear:left}.mw-parser-output .stack-clear-right{float:right;clear:right}.mw-parser-output .stack-left{float:left}.mw-parser-output .stack-right{float:right}.mw-parser-output .stack-margin-clear-left{float:left;clear:left;margin-right:1em}.mw-parser-output .stack-margin-clear-right{float:right;clear:right;margin-left:1em}.mw-parser-output .stack-margin-left{float:left;margin-right:1em}.mw-parser-output .stack-margin-right{float:right;margin-left:1em}}

/* end https://en.wikipedia.org/ */

</style><div class="stack mw-stack stack-right"><div>

<th style="text-align:center;padding-left:0.2em;padding-right:0.2em;font-size:90%;"> <a href="Binary_relation" title="Binary relation">binary relations</a> <style data-mw-deduplicate="TemplateStyles:r1129693374">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

</th></tr>

<tr>

<td><table style="text-align:center;"><tbody><tr style="vertical-align:middle;"><td style="padding-left:0.3em; padding-right:0.3em;;text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Symmetric_relation" title="Symmetric relation">Symmetric</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Antisymmetric_relation" title="Antisymmetric relation">Antisymmetric</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Connected_relation" title="Connected relation">Connected</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Well-founded_relation" title="Well-founded relation">Well-founded</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Join_and_meet" title="Join and meet">Has joins</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Join_and_meet" title="Join and meet">Has meets</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Reflexive_relation" title="Reflexive relation">Reflexive</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Reflexive_relation#Irreflexive" title="Reflexive relation">Irreflexive</a></td><td style="padding-left:0.3em; padding-right:0.3em;"> <a href="Asymmetric_relation" title="Asymmetric relation">Asymmetric</a></td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"></td><td></td><td></td><td> Total, Semiconnex</td><td></td><td></td><td></td><td></td><td> Anti- reflexive</td><td></td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Equivalence_relation" title="Equivalence relation">Equivalence relation</a></td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Preorder" title="Preorder">Preorder (Quasiorder)</a></td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Partial_order" class="mw-redirect" title="Partial order">Partial order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Total_preorder" class="mw-redirect" title="Total preorder">Total preorder</a></td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Total_order" title="Total order">Total order</a></td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Prewellordering" title="Prewellordering">Prewellordering</a></td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Well-quasi-ordering" title="Well-quasi-ordering">Well-quasi-ordering</a></td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Well-order" title="Well-order">Well-ordering</a></td><td> ✗</td><td> Y</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Lattice_(order)" title="Lattice (order)">Lattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Join-semilattice" class="mw-redirect" title="Join-semilattice">Join-semilattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Meet-semilattice" class="mw-redirect" title="Meet-semilattice">Meet-semilattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Strict_partial_order" class="mw-redirect" title="Strict partial order">Strict partial order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Weak_ordering#Strict_weak_orderings" title="Weak ordering">Strict weak order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> <a href="Strict_total_order" class="mw-redirect" title="Strict total order">Strict total order</a></td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"></td><td> <a href="Symmetric_relation" title="Symmetric relation">Symmetric</a></td><td> <a href="Antisymmetric_relation" title="Antisymmetric relation">Antisymmetric</a></td><td> <a href="Connected_relation" title="Connected relation">Connected</a></td><td> <a href="Well-founded_relation" title="Well-founded relation">Well-founded</a></td><td> <a href="Join_and_meet" title="Join and meet">Has joins</a></td><td> <a href="Join_and_meet" title="Join and meet">Has meets</a></td><td> <a href="Reflexive_relation" title="Reflexive relation">Reflexive</a></td><td> <a href="Reflexive_relation#Irreflexive" title="Reflexive relation">Irreflexive</a></td><td> <a href="Asymmetric_relation" title="Asymmetric relation">Asymmetric</a></td></tr><tr style="vertical-align:middle;"><td style="text-align:right;padding-left:0.6em; padding-right:1.2em; font-weight:bold;"> Definitions, for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b}</annotation>

</semantics>

</math><img src="./181523deba732fda302fd176275a0739121d3bc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.261ex; height:2.509ex;" alt="{\displaystyle a,b}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\neq \varnothing :}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\neq \varnothing :}</annotation>

</semantics>

</math><img src="./a538fab804c9428c4f7d4ca3ed214a97483c4260.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.698ex; height:2.676ex;" alt="{\displaystyle S\neq \varnothing :}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}">

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}</annotation>

</semantics>

</math><img src="./a18cac1ed3115c87d45b4d751de57124233a6e00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:7.712ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}">

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}</annotation>

</semantics>

</math><img src="./e9cc3f46e9f0b647ce6771396a975ef8d364674d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:13.643ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}">

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}</annotation>

</semantics>

</math><img src="./8c73cadd7ab7bf3b5257f5c505c756ec098902f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:11.97ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}">

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>exists</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./b7ec5a418cceeb68b9945ca75d31604719db4660.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:6.513ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}">

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>exists</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./b3386379a9406067b50b99e12241e9d7fab3369b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:6.395ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}">

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>exists</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./abff244e064dd72fd16781277ad3440b35bd767d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:6.395ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle aRa}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle aRa}</annotation>

</semantics>

</math><img src="./ba7fc1d9d50c65105d5edcb3478b5ca4172c54d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.224ex; height:2.176ex;" alt="{\displaystyle aRa}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{not }}aRa}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{not }}aRa}</annotation>

</semantics>

</math><img src="./8263f0c706367e5306eae1b9353034024639da23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.164ex; height:2.176ex;" alt="{\displaystyle {\text{not }}aRa}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}">

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}</annotation>

</semantics>

</math><img src="./a1aec245f8776556d3ad3fcdc18d4ba61929eccb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:8.683ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}" loading="lazy"></td></tr></tbody></table>

</td></tr>

<tr>

<td style="text-align:center;">Y indicates that the column's property is always true for the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the <a href="Homogeneous_relation" title="Homogeneous relation">homogeneous relation</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> be : for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b,c,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b,c,}</annotation>

</semantics>

</math><img src="./e6021b6ac503535d74098454c2a870a1b5c187d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.949ex; height:2.509ex;" alt="{\displaystyle a,b,c,}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle aRb}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle aRb}</annotation>

</semantics>

</math><img src="./c8b0b52168739fd16b254298771ec07b900e5a6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.991ex; height:2.176ex;" alt="{\displaystyle aRb}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle bRc}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle bRc}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle aRc.}</annotation>

</semantics>

</math><img src="./48e3d14d72455c36aab129326d6dceefafb3f12a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.648ex; height:2.176ex;" alt="{\displaystyle aRc.}" loading="lazy">

A term's definition may require additional properties that are not listed in this table.

</td></tr></tbody></table></div></div>

A <a href="Homogeneous_relation" title="Homogeneous relation">homogeneous relation</a> R on the set X is a transitive relation if,<a href="#cite_note-1">[1]</a>

Or in terms of <a href="First-order_logic" title="First-order logic">first-order logic</a>:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}</annotation>

</semantics>

where a R b is the <a href="Infix_notation" title="Infix notation">infix notation</a> for (a, b) ∈ R.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

As a non-mathematical example, the relation "is an ancestor of" is transitive. For example, if Amy is an ancestor of Becky, and Becky is an ancestor of Carrie, then Amy is also an ancestor of Carrie.

On the other hand, "is the birth mother of" is not a transitive relation, because if Alice is the birth mother of Brenda, and Brenda is the birth mother of Claire, then it does not follow that Alice is the birth mother of Claire. In fact, this relation is <a href="Antitransitive" class="mw-redirect" title="Antitransitive">antitransitive</a>: Alice can never be the birth mother of Claire.

Non-transitive, non-antitransitive relations include sports fixtures (playoff schedules), 'knows' and 'talks to'.

The examples "is greater than", "is at least as great as", and "is equal to" (<a href="Equality_(mathematics)" title="Equality (mathematics)">equality</a>) are transitive relations on various sets.

As are the set of real numbers or the set of natural numbers:

<dl><dd>whenever x > y and y > z, then also x > z</dd>

<dd>whenever x ≥ y and y ≥ z, then also x ≥ z</dd>

<dd>whenever x = y and y = z, then also x = z.</dd></dl>

More examples of transitive relations:

<ul><li>"is a <a href="Subset" title="Subset">subset</a> of" (set inclusion, a relation on sets)</li>

<li>"divides" (<a href="Divisor" title="Divisor">divisibility</a>, a relation on natural numbers)</li>

<li>"implies" (<a href="Material_conditional" title="Material conditional">implication</a>, symbolized by "⇒", a relation on <a href="Proposition" title="Proposition">propositions</a>)</li></ul>

Examples of non-transitive relations:

<ul><li>"is the <a href="Successor_function" title="Successor function">successor</a> of" (a relation on natural numbers)</li>

<li>"is a member of the set" (symbolized as "∈")<a href="#cite_note-2">[2]</a></li>

<li>"is <a href="Perpendicular" title="Perpendicular">perpendicular</a> to" (a relation on lines in <a href="Euclidean_geometry" title="Euclidean geometry">Euclidean geometry</a>)</li></ul>

The <a href="Empty_relation" class="mw-redirect" title="Empty relation">empty relation</a> on any set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is transitive<a href="#cite_note-3">[3]</a> because there are no elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b,c\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b,c\in X}</annotation>

</semantics>

</math><img src="./0f7e9f9e089acfdec5f7ec02f66f13be71667e1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.123ex; height:2.509ex;" alt="{\displaystyle a,b,c\in X}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle aRb}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle aRb}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle bRc}</annotation>

</semantics>

</math><img src="./93a62ff0d4c99429cb3465edecb65d2b1a53cf30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.768ex; height:2.176ex;" alt="{\displaystyle bRc}" loading="lazy">, and hence the transitivity condition is <a href="Vacuous_truth" title="Vacuous truth">vacuously true</a>. A relation R containing only one <a href="Ordered_pair" title="Ordered pair">ordered pair</a> is also transitive: if the ordered pair is of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,x)}</annotation>

</semantics>

</math><img src="./72f9e25892f6d000349b8bb6578a59567efbdd63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.503ex; height:2.843ex;" alt="{\displaystyle (x,x)}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"> the only such elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b,c\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b,c\in X}</annotation>

</semantics>

</math><img src="./0f7e9f9e089acfdec5f7ec02f66f13be71667e1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.123ex; height:2.509ex;" alt="{\displaystyle a,b,c\in X}" loading="lazy"> are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=b=c=x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=b=c=x}</annotation>

</semantics>

</math><img src="./bdb23e6defc6b271b81da398ef23111d8e5544a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.859ex; height:2.176ex;" alt="{\displaystyle a=b=c=x}" loading="lazy">, and indeed in this case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle aRc}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle aRc}</annotation>

</semantics>

</math><img src="./7fa8a450af6aba1999bff8edea021e583b059b01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.001ex; height:2.176ex;" alt="{\displaystyle aRc}" loading="lazy">, while if the ordered pair is not of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,x)}</annotation>

</semantics>

</math><img src="./72f9e25892f6d000349b8bb6578a59567efbdd63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.503ex; height:2.843ex;" alt="{\displaystyle (x,x)}" loading="lazy"> then there are no such elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b,c\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b,c\in X}</annotation>

</semantics>

</math><img src="./0f7e9f9e089acfdec5f7ec02f66f13be71667e1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.123ex; height:2.509ex;" alt="{\displaystyle a,b,c\in X}" loading="lazy"> and hence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

Vacuous transitivity is transitivity when in a relation there are no ordered pairs of the form (a,b) and (b,c).

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Closure_properties">Closure properties</h3></div>

<ul><li>The <a href="Converse_relation" title="Converse relation">converse</a> (inverse) of a transitive relation is always transitive. For instance, knowing that "is a <a href="Subset" title="Subset">subset</a> of" is transitive and "is a <a href="Superset" class="mw-redirect" title="Superset">superset</a> of" is its converse, one can conclude that the latter is transitive as well.</li>

<li>The intersection of two transitive relations is always transitive.<a href="#cite_note-4">[4]</a> For instance, knowing that "was born before" and "has the same first name as" are transitive, one can conclude that "was born before and also has the same first name as" is also transitive.</li>

<li>The union of two transitive relations need not be transitive. For instance, "was born before or has the same first name as" is not a transitive relation, since e.g. <a href="Herbert_Hoover" title="Herbert Hoover">Herbert Hoover</a> is related to <a href="Franklin_D._Roosevelt" title="Franklin D. Roosevelt">Franklin D. Roosevelt</a>, who is in turn related to <a href="Franklin_Pierce" title="Franklin Pierce">Franklin Pierce</a>, while Hoover is not related to Franklin Pierce.</li>

<li>The complement of a transitive relation need not be transitive.<a href="#cite_note-Derek.1964-5">[5]</a> For instance, while "equal to" is transitive, "not equal to" is only transitive on sets with at most one element.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Other_properties">Other properties</h3></div>

A transitive relation is <a href="Asymmetric_relation" title="Asymmetric relation">asymmetric</a> if and only if it is <a href="Irreflexive_relation" class="mw-redirect" title="Irreflexive relation">irreflexive</a>.<a href="#cite_note-6">[6]</a>

A transitive relation need not be <a href="Reflexive_relation" title="Reflexive relation">reflexive</a>. When it is, it is called a <a href="Preorder" title="Preorder">preorder</a>. For example, on set X = {1,2,3}:

<ul><li>R = { (1,1), (2,2), (3,3), (1,3), (3,2) } is reflexive, but not transitive, as the pair (1,2) is absent,</li>

<li>R = { (1,1), (2,2), (3,3), (1,3) } is reflexive as well as transitive, so it is a preorder,</li>

<li>R = { (1,1), (2,2), (3,3) } is reflexive as well as transitive, another preorder,</li>

<li>R = { (1,2), (2,3), (1,3) } is transitive, but not reflexive.</li></ul>

As a counter example, the relation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle <}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle <}</annotation>

</semantics>

</math><img src="./33737c89a17785dacc8638b4d66db3d5c8670de1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle <}" loading="lazy"> on the real numbers is transitive, but not reflexive.

<div class="mw-heading mw-heading2"><h2 id="Transitive_extensions_and_transitive_closure">Transitive extensions and transitive closure</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Transitive_closure" title="Transitive closure">Transitive closure</a></div>

Let R be a binary relation on set X. The transitive extension of R, denoted R1, is the smallest binary relation on X such that R1 contains R, and if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R1.<a href="#cite_note-7">[7]</a> For example, suppose X is a set of towns, some of which are connected by roads. Let R be the relation on towns where (A, B) ∈ R if there is a road directly linking town A and town B. This relation need not be transitive. The transitive extension of this relation can be defined by (A, C) ∈ R1 if you can travel between towns A and C by using at most two roads.

If a relation is transitive then its transitive extension is itself, that is, if R is a transitive relation then R1 = R.

The transitive extension of R1 would be denoted by R2, and continuing in this way, in general, the transitive extension of Ri would be Ri + 1. The transitive closure of R, denoted by R* or R∞ is the set union of R, R1, R2, ... .<a href="#cite_note-Liu112-8">[8]</a>

The transitive closure of a relation is a transitive relation.<a href="#cite_note-Liu112-8">[8]</a>

The relation "is the birth parent of" on a set of people is not a transitive relation. However, in biology the need often arises to consider birth parenthood over an arbitrary number of generations: the relation "is a birth ancestor of" is a transitive relation and it is the transitive closure of the relation "is the birth parent of".

For the example of towns and roads above, (A, C) ∈ R* provided you can travel between towns A and C using any number of roads.

<div class="mw-heading mw-heading2"><h2 id="Relation_types_that_require_transitivity">Relation types that require transitivity</h2></div>

<ul><li><a href="Preorder" title="Preorder">Preorder</a> – a <a href="Reflexive_relation" title="Reflexive relation">reflexive</a> and transitive relation</li>

<li><a href="Partially_ordered_set" title="Partially ordered set">Partial order</a> – an <a href="Antisymmetric_relation" title="Antisymmetric relation">antisymmetric</a> preorder</li>

<li><a href="Total_preorder" class="mw-redirect" title="Total preorder">Total preorder</a> – a <a href="Connected_relation" title="Connected relation">connected</a> (formerly called total) preorder</li>

<li><a href="Equivalence_relation" title="Equivalence relation">Equivalence relation</a> – a <a href="Symmetric_relation" title="Symmetric relation">symmetric</a> preorder</li>

<li><a href="Strict_weak_ordering" class="mw-redirect" title="Strict weak ordering">Strict weak ordering</a> – a strict partial order in which incomparability is an equivalence relation</li>

<li><a href="Total_ordering" class="mw-redirect" title="Total ordering">Total ordering</a> – a connected (total), antisymmetric, and transitive relation</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Counting_transitive_relations">Counting transitive relations</h2></div>

No general formula that counts the number of transitive relations on a finite set (sequence <a href="https://oeis.org/A006905" class="extiw external" title="oeis:A006905">A006905</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>) is known.<a href="#cite_note-9">[9]</a> However, there is a formula for finding the number of relations that are simultaneously reflexive, symmetric, and transitive – in other words, <a href="Equivalence_relation" title="Equivalence relation">equivalence relations</a> – (sequence <a href="https://oeis.org/A000110" class="extiw external" title="oeis:A000110">A000110</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>), those that are symmetric and transitive, those that are symmetric, transitive, and antisymmetric, and those that are total, transitive, and antisymmetric. Pfeiffer<a href="#cite_note-10">[10]</a> has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also Brinkmann and McKay (2005)<a href="#cite_note-11">[11]</a> and Mala (2022).<a href="#cite_note-12">[12]</a>

Since the reflexivization of any transitive relation is a <a href="Preorder" title="Preorder">preorder</a>, the number of transitive relations an on n-element set is at most 2n time more than the number of preorders, thus it is asymptotically <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{(1/4+o(1))n^{2}}}">

<msup>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{(1/4+o(1))n^{2}}}</annotation>

</semantics>

</math><img src="./c77239b3a63dcbb988eb7064f2ea8f87b4b50fd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.135ex; height:3.009ex;" alt="{\displaystyle 2^{(1/4+o(1))n^{2}}}" loading="lazy"> by results of Kleitman and Rothschild.<a href="#cite_note-13">[13]</a>

<caption>Number of n-element binary relations of different types

</caption>

<th>Elements

</th>

</th>

<th>

</th>

<th><a href="Reflexive_relation" title="Reflexive relation">Reflexive</a>

</th>

<th><a href="Symmetric_relation" title="Symmetric relation">Symmetric</a>

</th>

<th><a href="Preorder" title="Preorder">Preorder</a>

</th>

<th><a href="Partially_ordered_set" title="Partially ordered set">Partial order</a>

</th>

<th><a href="Strict_weak_ordering" class="mw-redirect" title="Strict weak ordering">Total preorder</a>

</th>

<th><a href="Total_order" title="Total order">Total order</a>

</th>

<th><a href="Equivalence_relation" title="Equivalence relation">Equivalence relation</a>

</th></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>5

</td></tr>

<tr>

<td>15

</td></tr>

<tr>

<td>n

</td>

<td>2n2

</td>

<td>

</td>

<td>2n(n−1)

</td>

<td>2n(n+1)/2

</td>

<td>

</td>

<td>

</td>

<td>∑n k=0 k!S(n, k)

</td>

<td>n!

</td>

</td></tr>

<tr>

</th>

</th>

</th>

</th>

</th>

</th>

</th>

</th>

</th>

</th></tr></tbody></table>

Note that S(n, k) refers to <a href="Stirling_numbers_of_the_second_kind" title="Stirling numbers of the second kind">Stirling numbers of the second kind</a>.

<div class="mw-heading mw-heading2"><h2 id="Related_properties">Related properties</h2></div>

A relation R is called <a href="Intransitivity" title="Intransitivity">intransitive</a> if it is not transitive, that is, if xRy and yRz, but not xRz, for some x, y, z.

In contrast, a relation R is called <a href="Antitransitive" class="mw-redirect" title="Antitransitive">antitransitive</a> if xRy and yRz always implies that xRz does not hold.

For example, the relation defined by xRy if xy is an <a href="Even_number" class="mw-redirect" title="Even number">even number</a> is intransitive,<a href="#cite_note-14">[14]</a> but not antitransitive.<a href="#cite_note-:0-15">[15]</a> The relation defined by xRy if x is even and y is <a href="Odd_number" class="mw-redirect" title="Odd number">odd</a> is both transitive and antitransitive.<a href="#cite_note-16">[16]</a>

The relation defined by xRy if x is the <a href="Successor_function" title="Successor function">successor</a> number of y is both intransitive<a href="#cite_note-17">[17]</a> and antitransitive.<a href="#cite_note-18">[18]</a> Unexpected examples of intransitivity arise in situations such as political questions or group preferences.<a href="#cite_note-19">[19]</a>

Generalized to stochastic versions (<a href="Stochastic_transitivity" title="Stochastic transitivity">stochastic transitivity</a>), the study of transitivity finds applications of in <a href="Decision_theory" title="Decision theory">decision theory</a>, <a href="Psychometrics" title="Psychometrics">psychometrics</a> and <a href="Utilitarianism" title="Utilitarianism">utility models</a>.<a href="#cite_note-20">[20]</a>

A <a href="Quasitransitive_relation" title="Quasitransitive relation">quasitransitive relation</a> is another generalization;<a href="#cite_note-Derek.1964-5">[5]</a> it is required to be transitive only on its non-symmetric part. Such relations are used in <a href="Social_choice_theory" title="Social choice theory">social choice theory</a> or <a href="Microeconomics" title="Microeconomics">microeconomics</a>.<a href="#cite_note-21">[21]</a>

Proposition: If R is a <a href="Univalent_relation" class="mw-redirect" title="Univalent relation">univalent</a>, then R;RT is transitive.

<dl><dd>proof: Suppose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xR;R^{T}yR;R^{T}z.}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xR;R^{T}yR;R^{T}z.}</annotation>

</semantics>

</math><img src="./8ed234baf4b6c2bfec571ad8f9b9d969b645fa40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.123ex; height:3.009ex;" alt="{\displaystyle xR;R^{T}yR;R^{T}z.}" loading="lazy"> Then there are a and b such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xRaR^{T}yRbR^{T}z.}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xRaR^{T}yRbR^{T}z.}</annotation>

</semantics>

</math><img src="./b9ad5395644aa5ba9532ac038d9cb6e5a714cbb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.282ex; height:3.009ex;" alt="{\displaystyle xRaR^{T}yRbR^{T}z.}" loading="lazy"> Since R is univalent, yRb and aRTy imply a=b. Therefore xRaRTz, hence xR;RTz and R;RT is transitive.</dd></dl>

Corollary: If R is univalent, then R;RT is an <a href="Equivalence_relation" title="Equivalence relation">equivalence relation</a> on the domain of R.

<dl><dd>proof: R;RT is symmetric and reflexive on its domain. With univalence of R, the transitive requirement for equivalence is fulfilled.</dd></dl>

<ul><li><a href="Transitive_reduction" title="Transitive reduction">Transitive reduction</a></li>

<li><a href="Intransitive_dice" title="Intransitive dice">Intransitive dice</a></li>

<li><a href="Rational_choice_theory" class="mw-redirect" title="Rational choice theory">Rational choice theory</a></li>

<li><a href="Hypothetical_syllogism" title="Hypothetical syllogism">Hypothetical syllogism</a> — transitivity of the material conditional</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFSmithEggenSt._Andre2006">Smith, Eggen & St. Andre 2006</a>, p. 145

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> However, the class of <a href="Von_Neumann_ordinal" class="mw-redirect" title="Von Neumann ordinal">von Neumann ordinals</a> is constructed in a way such that ∈ is transitive when restricted to that class.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFSmithEggenSt._Andre2006">Smith, Eggen & St. Andre 2006</a>, p. 146

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBianchiMauriHerzogVerardi2000" class="citation cs2">Bianchi, Mariagrazia; Mauri, Anna Gillio Berta; Herzog, Marcel; Verardi, Libero (2000-01-12), <a rel="nofollow" class="external text" href="https://www.degruyter.com/document/doi/10.1515/jgth.2000.012/html">"On finite solvable groups in which normality is a transitive relation"</a>, Journal of Group Theory, 3 (2), <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1515%2Fjgth.2000.012">10.1515/jgth.2000.012</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1433-5883">1433-5883</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204151127/https://www.degruyter.com/document/doi/10.1515/jgth.2000.012/html">archived</a> from the original on 2023-02-04, retrieved 2022-12-29</cite>

</li>

<li id="cite_note-Derek.1964-5">^ <a href="#cite_ref-Derek.1964_5-0">a</a> <a href="#cite_ref-Derek.1964_5-1">b</a> <cite id="CITEREFRobinson1964" class="citation cs2">Robinson, Derek J. S. (January 1964), <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/product/identifier/S0305004100037403/type/journal_article">"Groups in which normality is a transitive relation"</a>, Mathematical Proceedings of the Cambridge Philosophical Society, 60 (1): 21–38, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1964PCPS...60...21R">1964PCPS...60...21R</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0305004100037403">10.1017/S0305004100037403</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0305-0041">0305-0041</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119707269">119707269</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204151127/https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/abs/groups-in-which-normality-is-a-transitive-relation/E1EECC9F60124437962FBF9FDD8E81BA">archived</a> from the original on 2023-02-04, retrieved 2022-12-29</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFFlaškaJežekKepkaKortelainen2007" class="citation cs2">Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf">Transitive Closures of Binary Relations I</a> (PDF), Prague: School of Mathematics - Physics Charles University, p. 1, archived from <a rel="nofollow" class="external text" href="http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf">the original</a> (PDF) on 2013-11-02</cite> Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFLiu1985">Liu 1985</a>, p. 111

</li>

<li id="cite_note-Liu112-8">^ <a href="#cite_ref-Liu112_8-0">a</a> <a href="#cite_ref-Liu112_8-1">b</a> <a href="#CITEREFLiu1985">Liu 1985</a>, p. 112

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFFinch2003" class="citation cs2">Finch, Steven R. (2003), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304111410/http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf">Transitive relations, topologies and partial orders</a> (PDF), archived from <a rel="nofollow" class="external text" href="http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf">the original</a> (PDF) on 2016-03-04</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFPfeiffer2004" class="citation cs2">Pfeiffer, Götz (2004), <a rel="nofollow" class="external text" href="https://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">"Counting transitive relations"</a>, Journal of Integer Sequences, 7 (3) 04.3.2: 1–11, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2085342">2085342</a></cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFBrinkmannMcKay2005" class="citation cs2">Brinkmann, Gunnar; McKay, Brendan D. (2005), <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/journals/JIS/VOL8/McKay/mckay170.html">"Counting unlabelled topologies and transitive relations"</a>, Journal of Integer Sequences, 8 (2) 05.2.1: 1–7, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2134160">2134160</a></cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFMala2022" class="citation cs2">Mala, Firdous Ahmad (2022), "On the number of transitive relations on a set", Indian Journal of Pure and Applied Mathematics, 53 (1): 228–232, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs13226-021-00100-0">10.1007/s13226-021-00100-0</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=4387391">4387391</a></cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFKleitmanRothschild1970" class="citation cs2">Kleitman, D.; Rothschild, B. (1970), "The number of finite topologies", Proceedings of the American Mathematical Society, 25 (2): 276–282, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9939-1970-0253944-9">10.1090/S0002-9939-1970-0253944-9</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2037205">2037205</a></cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> since e.g. 3R4 and 4R5, but not 3R5

</li>

<li id="cite_note-:0-15"><a href="#cite_ref-:0_15-0">^</a> since e.g. 2R3 and 3R4 and 2R4

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> since xRy and yRz can never happen

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> since e.g. 3R2 and 2R1, but not 3R1

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> since, more generally, xRy and yRz implies x=y+1=z+2≠z+1, i.e. not xRz, for all x, y, z

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFDrum2018" class="citation cs2">Drum, Kevin (November 2018), <a rel="nofollow" class="external text" href="https://www.motherjones.com/kevin-drum/2018/11/preferences-are-not-transitive/">"Preferences are not transitive"</a>, Mother Jones, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20181129113105/https://www.motherjones.com/kevin-drum/2018/11/preferences-are-not-transitive/">archived</a> from the original on 2018-11-29, retrieved 2018-11-29</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFOliveiraZehaviDavidov2018" class="citation cs2">Oliveira, I.F.D.; Zehavi, S.; Davidov, O. (August 2018), "Stochastic transitivity: Axioms and models", Journal of Mathematical Psychology, 85: 25–35, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jmp.2018.06.002">10.1016/j.jmp.2018.06.002</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-2496">0022-2496</a></cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFSen1969" class="citation cs2"><a href="Amartya_Sen" title="Amartya Sen">Sen, A.</a> (1969), "Quasi-transitivity, rational choice and collective decisions", Rev. Econ. Stud., 36 (3): 381–393, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2296434">10.2307/2296434</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2296434">2296434</a>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0181.47302">0181.47302</a></cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFLiu1985" class="citation cs2">Liu, C.L. (1985), <a rel="nofollow" class="external text" href="https://archive.org/details/elementsofdiscre00liuc">Elements of Discrete Mathematics</a>, McGraw-Hill, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-07-038133-X</bdi></cite></li>

<li><cite id="CITEREFSmithEggenSt._Andre2006" class="citation cs2">Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (6th ed.), Brooks/Cole, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-534-39900-9</bdi></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFGrimaldi1994" class="citation cs2"><a href="Ralph_Grimaldi" title="Ralph Grimaldi">Grimaldi, Ralph P.</a> (1994), Discrete and Combinatorial Mathematics (3rd ed.), Addison-Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-19912-2</bdi></cite></li>

<li><a href="Gunther_Schmidt" title="Gunther Schmidt">Gunther Schmidt</a>, 2010. Relational Mathematics. Cambridge University Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-76268-7</bdi>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Transitivity">"Transitivity"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li><a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/triangle/remarkable.shtml">Transitivity in Action</a> at <a href="Cut-the-knot" class="mw-redirect" title="Cut-the-knot">cut-the-knot</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-06" href="https://en.wikipedia.org/wiki/?title=Transitive_relation&oldid=1299045990">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>